﻿#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

//606. 根据二叉树创建字符串
//https://leetcode.cn/problems/construct-string-from-binary-tree/
class Solution {
public:
    string tree2str(TreeNode* root) {
        if (root == nullptr)
            return "";
        string str = to_string(root->val);
        if (root->left || root->right) {
            str += '(';
            str += tree2str(root->left);
            str += ')';
        }
        if (root->right) {
            str += '(';
            str += tree2str(root->right);
            str += ')';
        }
        return str;
    }
};
//102. 二叉树的层序遍历 
// https://leetcode.cn/problems/binary-tree-level-order-traversal/
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        int levelSize = 0;
        if (root) {
            q.push(root);
            levelSize = 1;
        }
        vector<vector<int>> vv;
        while (!q.empty()) {
            vector<int> v;
            while (levelSize--) {
                TreeNode* front = q.front();
                q.pop();
                v.push_back(front->val);
                if (front->left)
                    q.push(front->left);
                if (front->right)
                    q.push(front->right);
            }
            vv.push_back(v);
            levelSize = q.size();
        }
        return vv;
    }
};

//107. 二叉树的层序遍历 II
//https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> q;
        int levelSize = 0;
        vector<vector<int>> vv;
        if (root) {
            q.push(root);
            levelSize = 1;
        }
        while (!q.empty()) {
            vector<int> v;
            while (levelSize--) {
                TreeNode* front = q.front();
                q.pop();
                v.push_back(front->val);
                if (front->left)
                    q.push(front->left);
                if (front->right)
                    q.push(front->right);
            }
            vv.push_back(v);
            levelSize = q.size();
        }
        reverse(vv.begin(), vv.end());
        return vv;
    }
};

//236. 二叉树的最近公共祖先
//https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
//第一种效率低，第二种效率高
class Solution {
public:
    bool InsInTree(TreeNode* root, TreeNode* x) {
        if (root == nullptr)
            return false;

        return root == x || InsInTree(root->left, x) ||
            InsInTree(root->right, x);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr)
            return nullptr;

        if (p == root || q == root)
            return root;

        bool pInleft = InsInTree(root->left, p);
        bool pInRight = !pInleft;

        bool qInleft = InsInTree(root->left, q);
        bool qInRight = !qInleft;

        if ((pInLeft && qInRight) || (qInLeft && pInRight))
            return root;
        else if (pInLeft && qInLeft)
            return lowestCommonAncestor(root->left, p, q);
        else
            return lowestCommonAncestor(root->right, p, q);
    }
};

class Solution {
public:
    bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path) {
        if (root == nullptr)
            return false;
        path.push(root);
        if (root == x)
            return true;
        if (GetPath(root->left, x, path))
            return true;
        if (GetPath(root->right, x, path))
            return true;
        path.pop();
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> pPath, qPath;
        GetPath(root, p, pPath);
        GetPath(root, q, qPath);
        while (qPath.size() != pPath.size()) {
            if (pPath.size() > qPath.size())
                pPath.pop();
            else
                qPath.pop();
        }
        while (pPath.top() != qPath.top()) {
            pPath.pop();
            qPath.pop();
        }
        return qPath.top();
    }
};

// JZ36 二叉搜索树与双向链表
//https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&&tqId=11179&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
class Solution {
public:
    void InOrder(TreeNode* cur, TreeNode*& prev) {
        if (cur == nullptr)
            return;
        InOrder(cur->left, prev);
        cur->left = prev;
        if (prev)
            prev->right = cur;
        prev = cur;
        InOrder(cur->right, prev);
    }
    TreeNode* Convert(TreeNode* pRootOfTree) {
        TreeNode* prev = nullptr;
        InOrder(pRootOfTree, prev);
        TreeNode* head = pRootOfTree;
        while (head && head->left) {
            head = head->left;
        }
        return head;
    }
};

//105. 从前序与中序遍历序列构造二叉树
//https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
class Solution {
public:
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& prei,
        int inbegin, int inend) {
        if (inbegin > inend)
            return nullptr;
        TreeNode* root = new TreeNode(preorder[prei]);
        int rooti = inbegin;
        while (rooti <= inend) {
            if (inorder[rooti] == preorder[prei])
                break;
            else
                rooti++;
        }
        ++prei;
        root->left = _buildTree(preorder, inorder, prei, inbegin, rooti - 1);
        root->right = _buildTree(preorder, inorder, prei, rooti + 1, inend);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
        return _buildTree(preorder, inorder, i, 0, inorder.size() - 1);
    }
};

//106. 从中序与后序遍历序列构造二叉树
//https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
class Solution {
public:
    TreeNode* _buildTree(vector<int>& postorder, vector<int>& inorder,
        int& posi, int inbegin, int inend) {
        if (inbegin > inend)
            return nullptr;
        TreeNode* root = new TreeNode(postorder[posi]);
        int rooti = inbegin;
        while (rooti <= inend) {
            if (inorder[rooti] == postorder[posi])
                break;
            else
                rooti++;
        }
        --posi;
        root->right = _buildTree(postorder, inorder, posi, rooti + 1, inend);
        root->left = _buildTree(postorder, inorder, posi, inbegin, rooti - 1);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int i = postorder.size() - 1;
        return _buildTree(postorder, inorder, i, 0, inorder.size() - 1);
    }
};

//144. 二叉树的前序遍历
//https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
//非递归
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        vector<int> v;
        while (cur || !st.empty()) {
            while (cur) {
                v.push_back(cur->val);
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* top = st.top();
            st.pop();
            cur = top->right;
        }
        return v;
    }
};
//递归
class Solution {
public:
    void preorder(TreeNode* root, vector<int>& ret) {
        if (root == nullptr) {
            return;
        }
        ret.push_back(root->val);
        preorder(root->left, ret);
        preorder(root->right, ret);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        preorder(root, ret);
        return ret;
    }
};

//94. 二叉树的中序遍历
//https://leetcode.cn/problems/binary-tree-inorder-traversal/
//非递归
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        vector<int> v;
        while (cur || !st.empty()) {
            while (cur) {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* top = st.top();
            st.pop();
            v.push_back(top->val);
            cur = top->right;
        }
        return v;
    }
};
//递归
class Solution {
public:
    void inorder(TreeNode* root, vector<int>& ret) {
        if (root == nullptr)
            return;
        inorder(root->left, ret);
        ret.push_back(root->val);
        inorder(root->right, ret);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        inorder(root, ret);
        return ret;
    }
};

//145. 二叉树的后序遍历
//https://leetcode.cn/problems/binary-tree-postorder-traversal/
//非递归
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        vector<int> v;
        TreeNode* prev = nullptr;
        while (cur || !st.empty()) {
            while (cur) {
                st.push(cur);
                cur = cur->left;
            }

            TreeNode* top = st.top();

            //右为空，或者 右子树已经访问过了(上一个访问的节点是右子树的根)，可以访问根节点
            if (top->right == nullptr || top->right == prev) {
                v.push_back(top->val);
                st.pop();
                prev = top;
            }
            else {
                cur = top->right;
            }
        }
        return v;
    }
};
//递归
class Solution {
public:
    void postorder(TreeNode* root, vector<int>& ret) {
        if (root == nullptr) {
            return;
        }
        postorder(root->left, ret);
        postorder(root->right, ret);
        ret.push_back(root->val);
    }

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        postorder(root, ret);
        return ret;
    }
};

class Solution {
public:
    struct Compare {
        bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) const {
            return kv1.second > kv2.second || (kv1.second == kv2.second && kv1.first < kv2.first);
        }
    };
    
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> countMap;
        for(auto& str : words) {
            countMap[str]++;
        }
        
        multiset<pair<string, int>, Compare> sortSet(countMap.begin(), countMap.end());
        
        vector<string> ret;
        auto it = sortSet.begin();
        while(k--) {
            ret.push_back(it->first);
            ++it;
        }
        
        return ret;
    }
};
/*这段代码实现了一个函数 `topKFrequent`，用于找到给定字符串数组中出现频率最高的前 k 个字符串。

首先，定义了一个结构体 `Compare`，其中重载了函数调用运算符 `operator()`，用于比较两个键值对的大小。比较规则是先按照出现频率从大到小排序，如果频率相同则按照字符串的字典序排序。

在 `topKFrequent` 函数中，首先创建了一个 `map` 类型的变量 `countMap`，用于统计每个字符串出现的次数。遍历给定的字符串数组 `words`，对每个字符串进行计数。

接下来，创建了一个 `multiset` 类型的变量 `sortSet`，使用 `countMap` 的键值对初始化。`multiset` 是一个有序容器，根据 `Compare` 结构体中定义的比较规则对键值对进行排序。

然后，创建一个空的字符串向量 `ret`，用于存储出现频率最高的前 k 个字符串。

通过迭代器 `it` 遍历 `sortSet`，将前 k 个字符串依次添加到 `ret` 中。

最后，返回存储了出现频率最高的前 k 个字符串的向量 `ret`。

这段代码的思路是通过统计字符串出现的次数，并使用自定义的比较规则对键值对进行排序，然后取出前 k 个字符串作为结果返回。*/